//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
using namespace std;
string longestPalindrome(string s) {
    if (s.length()<=0)return s;

    int n = s.length();
    //定义状态数组
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    string res = "";
    res += s[0];
    //初始化， 对角线为true
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
    }
    //状态转移,先控制列
    for (int j = 1; j < n ; j++) {//列
        for (int i = 0; i < j; i++) {//行, 不等于
            //【i，j】
            bool  isCharEqual = s[i]==s[j];
            if(j-i==1){
                dp[i][j] = isCharEqual;
            }else if(!isCharEqual){
                dp[i][j] = false;
            }else{
                dp[i][j] = dp[i+1][j-1];
            }
            if (dp[i][j] && j-i+1>res.length()){
                res = s.substr(i, j-i+1);
            }
        }
    }
    return res;
}